[백준] 1932 - 정수삼각형 (파이썬)
November 03, 2021
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
풀이
크기가 1인 삼각형,
크기가 2인 삼각형,
크기가 3인 삼각형,
… 을 차례로 생각해보다 보면 풀 수 있다.
첫 층에서 마지막 층으로 내려오면서, 각 숫자를 해당 위치까지 오면서 만들 수 있는 최댓값으로 갱신한다.
7
7+3=10 7+8=15
10+8=18 15+1=16 15+0=15
18+2=20 18+7=25 16+4=20 15+4=19
... 이런 식으로 만들어지게 된다.
이걸 잘 살펴보면 해당 숫자가 가장 왼쪽 또는 가장 오른쪽인 경우에는 선택지가 하나밖에 없고, 가운데 위치한 경우에는 바로 윗층의 대각선 왼쪽 숫자 / 대각선 오른쪽 숫자 중 큰 값을 선택해 더해나가게 된다.
n = int(input())
triangle = [[] for _ in range(n)]
for i in range(n):
triangle[i] = list(map(int, input().split(" ")))
for i in range(1, n):
for j in range(len(triangle[i])):
if j == 0: # 해당 숫자가 가장 왼쪽
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1: # 해당 숫자가 가장 오른쪽
triangle[i][j] += triangle[i-1][j-1]
else: # 해당 숫자가 가운데 위치 - 위층에서 대각선 왼쪽 수 / 대각선 오른쪽 수 둘 중 큰 값과 더함
triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
print(max(triangle[-1])) # 가장 아랫층에는 최종 누적값이 만들어지게 됨. 그 중 최댓값 출력![[hyem]](/static/114fe002cfffaf65598b36268e468ff7/a12fc/profile.png)